
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2182. -- [Spoj1479]The GbAaY Kingdom最小直径生成树 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2182: [Spoj1479]The GbAaY Kingdom最小直径生成树</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>259 MB<br><span class=green>Submit: </span>177&nbsp;&nbsp;<span class=green>Solved: </span>27<br>[<a href='submitpage.php?id=2182'>Submit</a>][<a href='problemstatus.php?id=2182'>Status</a>][<a href='bbs.php?id=2182'>Discuss</a>]</center><h2>Description</h2><div class=content><p><span style="font-size: medium">Jiajia is the king of the GbAaY Kingdom. He always squeezes his 20 ministers as coolies. There are n cities and m two-way roads connecting cities in the kingdom. Because of the increasing of the oil fee, he want to simplify the road system in the GbAaY Kingdom to save the traffic cost. Thus, some of roads will be removed. But he requests the ministers guarantee that there is always a path between any two cities. GbAaY Minister Loner suggests Jiajia for the convenience of the traffic management, the farthest distance between cities should be minimal. Unhesitatingly, Jiajia agrees this resolution. As the GbAaY Kingdom's minister (cooly), you must work hard for Jiajia to make the simplification plan. JiaJia是GbAaY王国的王（高贵ING&hellip;&hellip;） 他每天都要挤出20分钟用在做菜上面。 他的王国有N个城市，由M条双向边所连接着。 因为石油的价格上涨，他想把GbAaY王国的交通简化，好节约交通花费。 于是，有些路径需要被移除 但是依然保证移除之后依然有路径连接任意两个城市。 GbAaY的大臣Loner建议JiaJia，为了使交通管理的方便， 整个城市中最长的一条路径需要他的值最小 JiaJia迅速答应了大臣的这个决定。 你作为GbAaY王国的一个大臣，你必须帮助JiaJia简化这个问题 </span></p></div><h2>Input</h2><div class=content><p><span style="font-size: medium">The first line contains two integers n, m (1 &lt;= n &lt;= 200, n - 1 &lt;= m &lt;= 50000). Each line of the following m lines contains three integers u, v, w (u != v, 0 &lt;= w &lt;= 10^5). They denote there is a road with length w between city u and city v.</span></p>
<p><span style="font-size: medium"> 第一行有两个正整数N M(1 &lt;= n &lt;= 200, n - 1 &lt;= m &lt;= 50000). 接着M行每行三个正整数 u,v,w (u != v, 0 &lt;= w &lt;= 10^5) 描述一条连接u,v的双向边的长度是w</span></p></div><h2>Output</h2><div class=content><p><span style="font-size: medium">The first line contains one integer which is the farthest distance between cities after the simplification. 输出第一行有一个正整数表示在简化交通后最远的两个城市的距离 </span></p></div><h2>Sample Input</h2>
			<div class=content><span class=sampledata><br />
3 3<br />
1 2 1<br />
2 3 1<br />
1 3 1<br />
<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>2</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=2182'>Submit</a>][<a href='problemstatus.php?id=2182'>Status</a>][<a href='bbs.php?id=2182'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
